Title:
Composition de services : algorithmes et complexité.

Author:
Fahima Cheikh
(CRIL, Université d'Artois)

Keywords:
Composition de services, automates, relations d’équivalence et de préordre
décidabilité et complexité.

Abstract:
Le problème de la combinaison des services, autrement appelé problème de la
composition, constitue le foyer d'une intense activité de recherche.
Composer les services entre eux, c'est entrelacer leurs séquences
d'actions, de manière à obtenir des séquences qui satisfassent les
exigences des clients. Le problème de la composition de services est
difficile à résoudre en général. 

Dans mes travaux je considére des services qui peuvent à la fois exécuter
des actions de communications ainsi que des actions internes. De plus, des
conditions peuvent être exigées et des effets peuvent être appliqués sur
les transitions. Formellement, les services sont représentés par des
automates communicants conditionnels.  

J'ai défini, pour ce modèle, le problème de la composition et j'ai étudié
sa décidabilité pour différentes relations d’équivalence et de préordre à
savoir : l’inclusion de traces, l’équivalence de traces, la simulation et
la bisimulation.    

Suite aux résultats de décidabilité obtenus, j'ai proposé trois variantes
pour le modèle initial. Pour chacune d’elles, j'ai définis le problème de
la composition et j'ai étudié sa complexité pour les relations citées ci-
dessus.